package class08;

public class Code09_NQueens {

	/**
	 * 暴力递归法
	 * @param n
	 * @return
	 */
	public static int num1(int n) {
		if (n < 1) {
			return 0;
		}
		int[] record = new int[n]; // record[i] -> 记录第i行的皇后放在了第几列
		return process1(0, record, n);
	}

	// n是终止位置。 在 0~n-1 行去尝试
	public static int process1(int i, int[] record, int n) {
		// base case  i 来到了终止位置，说明这一种符合条件
		if (i == n) {
			return 1;
		}
		int res = 0;

		// j代表列
		for (int j = 0; j < n; j++) {

			// isValid() 当前i行的皇后，放在j列，会不会跟之前[0...i-2]行的皇后，共行共列共斜线
			// 如果是，认为无效
			// 如果不是，认为有效
			if (isValid(record, i, j)) {
				record[i] = j;
				res += process1(i + 1, record, n);
			}
		}
		return res;
	}

	// record[0..i-1]你需要看，record[i...]不需要看。 也就是说，我走到了i位置，只要关注是否与之前的共不共，而不需要关注后面的
	// 该函数返回 i行皇后放在了j列，是否是有效的
	public static boolean isValid(int[] record, int i, int j) {
		for (int k = 0; k < i; k++) {
			// 前一部分代表共列；后一部分代表共斜线
			// 共斜线利用了斜率为1，斜率k=(y2-y1)/(x2-x1) 要么45度要么135度
			if (j == record[k] || Math.abs(i - k) == Math.abs(j - record[k])) {
				return false;
			}
		}
		return true;
	}


	/**
	 * 思路与num1一致，但更加快，用位运算做加速
	 * @param n
	 * @return
	 */
	// 请不要超过32皇后问题
	public static int num2(int n) {
		if (n < 1 || n > 32) {
			return 0;
		}
		// upperLimit代表上限，如果8皇后问题，就认为左面全是0，最后八位为1
		// 假设是13皇后，1<<N 代表1向左位移13位，也就是14位为1，其余位为0；再-1，也就是1到13位为1，其余位都为0
		// -1的二进制全部位数都为1
		int upperLim = n == 32 ? -1 : (1 << n) - 1;
		return process2(upperLim, 0, 0, 0);
	}

	// colLim 列的限制，1的位置不能放皇后，0的位置可以
	// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
	// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
	public static int process2(int upperLim, int colLim, int leftDiaLim,
			int rightDiaLim) {
		// base case
		if (colLim == upperLim) { // 列限制信息和limit一样了，也就是全部都是1了，说明N个皇后都放完了
			return 1;
		}

		int pos = 0;
		int mostRightOne = 0;

		// 来到当前行的总限制 colLim | leftDiaLim | rightDiaLim
		// pos上为0的位置代表现在能 放置皇后的位置
		pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
		int res = 0;
		while (pos != 0) { // 有多少位的1运行多少次
			mostRightOne = pos & (~pos + 1); // 提取出pos最右面的那个1
			pos = pos - mostRightOne; // 把该位置置为0，下次就不用他了
			res += process2(upperLim, colLim | mostRightOne, // 列限制的更新
					(leftDiaLim | mostRightOne) << 1, // 左斜限制的更新
					(rightDiaLim | mostRightOne) >>> 1); // 右斜限制的更新
		}
		return res;
	}




	public static void main(String[] args) {
		int n = 14;

		long start = System.currentTimeMillis();
		System.out.println(num2(n));
		long end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

		start = System.currentTimeMillis();
		System.out.println(num1(n));
		end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

	}
}
